package advance.day01;

/**
 * 描述：
 *      在字符串的末尾添加最少的字符，使形成的大串包含两个原始串
 *      思路：求出原始字符的公共前缀，然后将公共前缀后面的字符复制一份添加到末尾，kmp求next数组
 * @author hl
 * @version 1.0
 * @date 2020/11/4 16:04
 */
public class KMP_ShortHaveTwice {
    public static String shortHaveTwice(String str){
        if (str == null || str.length() == 0) {
            return null;
        }
        char[] chs = str.toCharArray();
        if (str.length() == 1) {
            return str + str;
        }
        if (str.length() == 2) {
            return chs[0] == chs[1] ? (str + chs[0]) : (str + str);
        }
        int endNext = getEndNextLength(str);
        return str + str.substring(endNext);
    }

    private static int getEndNextLength(String str) {
        int[] next = new int[str.length() + 1];
        next[0] = -1;
        next[1] = 0;
        int index = 2;
        int cn = 0;
        while(index < next.length){
            if (str.charAt(index - 1) == str.charAt(cn)) {
                next[index++] = ++cn;
            }else if (cn > 0) {
                cn = next[cn];
            }else{
                next[index++] = 0;
            }
        }
        return next[next.length - 1];
    }
    public static void main(String[] args) {
        String test1 = "a";
        System.out.println(shortHaveTwice(test1));

        String test2 = "aa";
        System.out.println(shortHaveTwice(test2));

        String test3 = "ab";
        System.out.println(shortHaveTwice(test3));

        String test4 = "abcdabcd";
        System.out.println(shortHaveTwice(test4));

        String test5 = "abracadabra";
        System.out.println(shortHaveTwice(test5));

    }
}
